# Classes definitions and expansions

class Array
	
	# Pretty print for a list of vertices
	def pp
		self.collect{ |v| v.get_label unless v.nil? }.inspect
	end

	# Copy an array to another
	def copy
		Array.new(self)
	end

end

class Graph

	def initialize(vertices = [])
		@v = vertices
	end

	def add_vertex(v)
		@v << v
	end

	def get_vertices
		@v
	end

	def n
		@v.size
	end

	def get_vertex(i)
		@v[i]
	end

	def print_matrix
		output = '  ' + @v.collect{ |v| v.get_label }.join(' ') + "\n"
		@v.each do |v|
			output += v.get_label + ' '
			@v.each { |u| output += v.is_connected_to?(u) ? '1 ' : '0 ' }
			output += "\n"
		end
		output
	end

	# Lexicographic Breadth First Search - From Wikipédia
	def lbfs
		sigma = [@v.copy]
		output = []
		replaced = [0]
		while !sigma.empty? do
			v = sigma[0].shift
			output << v
			sigma.delete_at(0) if sigma[0].empty?
			replaced.fill(0)
			v.get_neighbors.each do |w|
				s = nil
				sigma.each do |set|
					if set.include?(w)
						s = set
						break
					end
				end
				next if s.nil?
				pos = sigma.index(s)
				new_pos = pos
				if replaced[pos] == 1
					sigma[pos-1] << w
				else
					sigma.insert(pos,[w])
					new_pos += 1
					replaced.insert(pos,0)
				end
				s.delete(w)
				if s.empty?
					sigma.delete_at(new_pos)
					replaced.delete_at(new_pos)
				else
					replaced[new_pos] = 1
				end
			end
		end
		output
	end
	
	# Returns true if the graph is a chordal graph
	# Reference: http://en.wikipedia.org/wiki/Lexicographic_breadth-first_search#Chordal_graphs
	def is_chordal?
		set = self.lbfs.reverse
		@v.each do |v|
			w = v.closest_prior_neighbor(set)
			next if w.nil?
			return false if !((v.get_neighbors & set[set.index(w)+1..set.size-1]) - (w.get_neighbors & set[set.index(w)+1..set.size-1])).empty?
		end
		true
	end

	def cliques
		cliques = []
		peo = self.lbfs.reverse
		peo.each do |v|
			clique = [v]
			v.get_neighbors.each do |u|
				clique << u if peo.index(u) > peo.index(v)
			end
			cliques << clique
		end
		maximals = []
		cliques.each_index do |i|
			maximal = true
			cliques.each_index do |j|
				next if i == j
				maximal = false if (cliques[i] - cliques[j]).empty?
			end
			maximals << cliques[i] if maximal
		end
		maximals
	end

end

class Vertex

	def initialize(label = "")
		@label = label
		@neighbors = []
	end

	def connect_to(v)
		@neighbors << v
	end

	def is_connected_to?(v)
		@neighbors.include?(v)
	end

	def get_neighbors
		@neighbors
	end

	def get_label
		@label
	end

	def closest_prior_neighbor(set = [])
		(set.index(self) + 1).upto(set.size - 1) do |i|
			return set[i] if self.is_connected_to?(set[i])
		end
		nil
	end

end
